package gold.contest;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6058 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        Map<Integer, Long> con2Memo = new HashMap<>();
        Map<Integer, Long> con9Memo = new HashMap<>();
        int factor = 1000000007;

        public int countTexts(String pressedKeys) {
            TreeMap<Integer, Integer> con2Cnt = new TreeMap<>();
            TreeMap<Integer, Integer> con9Cnt = new TreeMap<>();
            int i = 1, curChStartPos = 0;
            char curCh = pressedKeys.charAt(0);
            while (i < pressedKeys.length()) {
                while (i < pressedKeys.length() && pressedKeys.charAt(i) == curCh) i++;
                int cnt = i - curChStartPos;
                if (curCh <= '8' && curCh >= '2' && curCh != '7') con2Cnt.put(cnt, con2Cnt.getOrDefault(cnt, 0) + 1);
                else con9Cnt.put(cnt, con9Cnt.getOrDefault(cnt, 0) + 1);
                if (i < pressedKeys.length()) {
                    curCh = pressedKeys.charAt(i);
                    curChStartPos = i;
                }
            }

            init2Memo(con2Cnt.isEmpty() ? 1 : con2Cnt.lastKey());
            init9Memo(con9Cnt.isEmpty() ? 1 : con9Cnt.lastKey());
            long ans = 1L;

            for (Integer cnt : con2Cnt.keySet()) {
                for (int j = 0; j < con2Cnt.get(cnt); j++) {
                    ans = (ans * con2Memo.get(cnt)) % factor;
                }
            }

            for (Integer cnt : con9Cnt.keySet()) {
                for (int j = 0; j < con9Cnt.get(cnt); j++) {
                    ans = (ans * con9Memo.get(cnt)) % factor;
                }
            }

            return (int) ans;
        }

        public void init2Memo(int up) {
            con2Memo.put(1, 1L);
            con2Memo.put(2, 2L);
            con2Memo.put(3, 4L);
            for (int i = 4; i <= up; i++) {
                con2Memo.put(i, (con2Memo.get(i - 1) + con2Memo.get(i - 2) + con2Memo.get(i - 3)) % factor);
            }
        }

        public void init9Memo(int up) {
            con9Memo.put(1, 1L);
            con9Memo.put(2, 2L);
            con9Memo.put(3, 4L);
            con9Memo.put(4, 8L);

            for (int i = 5; i <= up; i++) {
                con9Memo.put(i, (con9Memo.get(i - 1) + con9Memo.get(i - 2) + con9Memo.get(i - 3) + con9Memo.get(i - 4)) % factor);
            }
        }
    }

    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.countTexts("22233"));
//        System.out.println(solution.countTexts("222222222222222222222222222222222222"));
        System.out.println(solution.countTexts("55555555999977779555"));
    }

    public static void main(String[] args) throws Exception {
        LC6058 an = new LC6058();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
